using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStructure
{
    /// <summary>
    /// 最大堆(是完全二叉树)
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class MaxHeap<T> where T : IComparable<T>
    {
        /// <summary>
        /// 使用数组存储堆元素
        /// </summary>
        private T[] heap;
        
        private int count;
        
        public MaxHeap(int capacity)
        {
            //堆从1开始存储元素
            heap = new T[capacity + 1];
            count = 0;
        }

        public MaxHeap() : this(10) { }


        public int Count => count;

        public bool IsEmpty => count == 0;
        
        public void Insert(T t)
        {
            if (count == heap.Length - 1)
                ResetCapacity(heap.Length * 2);
            heap[count + 1] = t;
            count++;
            Swim(count);
        }
        
        /// <summary>
        /// 删除堆顶元素
        /// </summary>
        /// <returns></returns>
        public T RemoveMax()
        {
            if(IsEmpty)
                throw new InvalidOperationException("堆为空");
            Swap(1, count);
            T max = heap[count];
            heap[count] = default;
            count--;
            
            Sink(1);
            
            if(count == (heap.Length - 1)/4)
                ResetCapacity(heap.Length/2);

            return max;
        }

        public T Max()
        {
            if (IsEmpty)
                throw new InvalidOperationException("堆为空");
            return heap[1];
        }
        
        /// <summary>
        /// 元素下沉
        /// </summary>
        /// <param name="v">元素索引</param>
        //下沉操作
        private void Sink(int k)
        {
            //有左孩子
            while (2 * k <= count)
            {
                int j = 2 *k;
                
                //如果有右孩子且右孩子大于左孩子
                if (j +1 <= count && heap[j + 1].CompareTo(heap[j]) > 0)
                    j++;//j指向右孩子

                //如果当前节点大于等于孩子节点
                if (heap[k].CompareTo(heap[j]) >= 0)
                    break;

                //交换当前节点和孩子节点
                Swap(k, j);
                k = j;
            }
        }

        /// <summary>
        /// 元素上浮
        /// </summary>
        /// <param name="k"></param>
        private void Swim(int k)
        {
            //如果当前节点比父节点大，则交换
            while (k > 1 && heap[k].CompareTo(heap[k/2]) > 0)
            {
                Swap(k,k/2);
                k = k/2;
            }
        }

        private void Swap(int k, int v)
        {
            T temp = heap[k];
            heap[k] = heap[v];
            heap[v] = temp;
        }
    

        private void ResetCapacity(int newCapacity)
        {
            T[] temp = new T[newCapacity];
            for (int i = 1; i <= count; i++)
                temp[i] = heap[i];
            heap = temp;
        }
        public override string ToString()
        {
            StringBuilder SB = new StringBuilder();
            SB.AppendLine("[]");
            for (int i = 1; i<= count; i++)
            {
                SB.Append(heap[i]);
                if (i == count)
                    SB.Append(",");
            }
            SB.Append("]");
            return SB.ToString();
        }
    }
}